package 代码记录.指定公司代码练习记录.面试手撕2024.幂律科技;

public class Test1 {
    // 从上到下找到最短路径（n个数字之和最小,n为矩阵的行数），可以从第一行中的任何元素开始，
    // 只能往下层走，同时只能走向相邻的节点，例如图中第一排 2 只能走向 第二排的 7、3；
    // 第二排的 7 可以走向第三排的 6、2、9
    //
    // | 5    | 8    | 1    | 2    |
    // | 4    | 1    | 7    | 3    |
    // | 3    | 6    | 2    | 9    |
    //
    // Input: [
    //     [5, 8, 1, 2],
    //     [4, 1, 7, 3],
    //     [3, 6, 2, 9]
    // ]
    // Output: 4

    /**
     * 这道题就是这样的作法
     * 这道题最好用动态规划算法做，类似于力扣：64. 最小路径和
     */
    public static void main(String[] args) {
        int[][] matrix = new int[][]{
                {5, 8, 1, 2},
                {4, 1, 7, 3,},
                {3, 6, 2, 9}
                //3 (i + 1,j - 1)
                //6 (i + 1,j)
                //2 (i + 1,j + 1)
        };
        int res = Integer.MAX_VALUE;
        for(int i = 0;i < matrix[0].length;i++){
            int temp = dfs(matrix, 0, i);
            res = Math.min(temp,res);
        }
        System.out.println(res);
    }
    private static int dfs(int[][] arr, int i, int j){
        if(i < 0 || i >= arr.length || j < 0 || j >= arr[0].length){
            return Integer.MAX_VALUE;//下面Math.min()了,肯定要最大值
        }
        if(i == arr.length - 1){
            return arr[i][j];
        }
        int min = 0;
        int a = dfs(arr,i + 1,j - 1);
        int b = dfs(arr,i + 1,j);
        int c = dfs(arr,i + 1,j + 1);
        min = Math.min(a,Math.min(b,c));
        return arr[i][j] + min;
    }
}
